#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    vector<vector<int>> res;
    vector<int> path;
    void dfs(vector<int> &candidates, int target, int index)
    {
        if (target == 0)
        {
            res.push_back(path);
            return;
        }
        for (int i = index; i < candidates.size(); i++)
        {
            if (candidates[i] <= target)
            {
                if (i > index && candidates[i] == candidates[i - 1])
                    continue; //去重，注意已经排序
                path.push_back(candidates[i]);
                dfs(candidates, target - candidates[i], i + 1); //试探
                path.pop_back();                                //撤回
            }
        }
    }
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        //比上一个多一步去重
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0);
        return res;
    }
};